package com.desin.modle.sorts;

/**
 * 计数排序
 *
 * 理解思想最重要，理解思想之后就方便写代码了！！！！！！
 */
public class CountingSort {

    public void countingSort(int[] a,int n){
        if(n<=1){
            return;
        }

        //查找数据的范围
        int max = a[0];
        for(int i=0;i<n;i++){
            if(max<a[i]){
                max = a[i];
            }
        }

        //构建桶，并且桶内的数据是数组a内相同元素的个数，桶的下标是元素的值
        int[] c = new int[max + 1];
        for(int i=0;i<n;i++){
            c[a[i]] = c[a[i]] + 1;
        }

        //转换桶，将桶内的数据变更为累计小于该元素值的个数
        for(int i=1;i<c.length;i++){
            c[i] = c[i-1] + c[i];
        }

        //构建一个新的数组r，存放数组a中每个值所在r的位置
        int[] r = new int[n];
        for(int i=n-1;i>=0;i--){
            int index = c[a[i]]-1;
            r[index] = a[i];
            c[a[i]]--;
        }

        //替换数组r到a内
        for(int i=0;i<n;i++){
            a[i] = r[i];
        }
    }
}
